package temp;

/**
 * Created by yzy on 2020-04-14 19:32
 */
public class TopKQuestion {

    public static void main(String[] args) {

    }

    private static int kthLargestElement(int[] arr, int k){
        int[] minTopHeap = createMinTopHeap(arr, k);
        for(int i=k; k<arr.length; i++){
            if(arr[i] > minTopHeap[0]){
                putMinTopHeap(minTopHeap, arr[i]);
            }
        }
        return minTopHeap[0];
    }


    private static int[] createMinTopHeap(int[] arr, int k){
        int[] heap = new int[k];
        for(int i=0; i<k; i++){
            int val = arr[i];
            int childIdx = i;
            int parentIdx = (i-1)/2;
            while(parentIdx>0 && heap[parentIdx] > val){
                heap[childIdx] = heap[parentIdx];
                childIdx = parentIdx;
                parentIdx = (parentIdx-1)/2;
            }
            heap[childIdx] = val;
        }
        return heap;
    }

    private static void putMinTopHeap(int[] heap, int val){
        heap[0] = val;
        int parent=0;
        int heapLength = heap.length;
        while(parent < heapLength){
            int leftChild = parent * 2 + 1;
            int rightChild = parent * 2 + 2;
            int minIdx = parent;
            if(leftChild < heapLength && heap[leftChild] < heap[minIdx]){
                minIdx = leftChild;
            }
            if(rightChild < heapLength && heap[rightChild] < heap[minIdx]){
                minIdx = rightChild;
            }

            // 如果minIdx没有改变，说明已经顶堆已经构建完成，可以直接返回
            if(parent == minIdx){
                return;
            }

            // 否则，交换元素，继续往下
            int tmpVal = heap[minIdx];
            heap[minIdx] = heap[parent];
            heap[parent] = tmpVal;
            parent = minIdx;

        }
        return;
    }
}
